package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * @author feizns
 * @since 2020/3/9
 */
public class Connect2 {

    public static void main(String[] args) {
        new Connect2().connect(create());
    }

    private static Node create() {
        Node ret = new Node(0);
        ret.left = new Node(1);
        ret.right = new Node(2);
        return ret;
    }

    public Node connect(Node root) {
        if ( root == null )
            return null;
        Node level = root;
        while ( level != null ) {
            Node prev = null;
            Node curt = level;
            level = null;
            while ( curt != null ) {
                if ( curt.left != null ) {
                    if ( level == null )
                        level = curt.left;
                    if ( prev != null )
                        prev.next = curt.left;
                    prev = curt.left;
                }
                if ( curt.right != null ) {
                    if ( level == null )
                        level = curt.right;
                    if ( prev != null )
                        prev.next = curt.right;
                    prev = curt.right;
                }
                curt = curt.next;
            }
        }
        return root;
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

}
